<div class="tmd-doc">
﻿<h1>Bounds Check Elimination</h1>

<p>
Go is a memory safe language.
In array/slice element indexing and subslice operations,
Go runtime will check whether or not the involved indexes are out of range.
If an index is out of range, a panic will be produced to prevent the invalid index from doing harm.
This is called bounds check.
Bounds checks make our code run safely, on the other hand, they also make our code run a little slower.
</p>

<p>
Since Go Toolchain 1.7, the standard Go compiler
has used a new compiler backend, which based on SSA (static single-assignment form).
SSA helps Go compilers effectively use optimizations like
<a href="https://en.wikipedia.org/wiki/Bounds-checking_elimination">BCE</a> (bounds check elimination)
and <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">CSE</a> (common subexpression elimination).
BCE can avoid some unnecessary bounds checks, and CSE can avoid some duplicate calculations,
so that the standard Go compiler can generate more efficient programs.
Sometimes the improvement effects of these optimizations are obvious.
</p>

<p>
This article will list some examples to show how BCE works with the standard Go compiler 1.7+.
</p>

<p>
For Go Toolchain 1.7+, we can use <code>-gcflags="-d=ssa/check_bce"</code> compiler flag to
show which code lines still need bounds checks.
</p>

<h3>Example 1</h3>

<div>
<pre class="line-numbers must-line-numbers"><code class="language-go">// example1.go
package main

func f1(s []int) {
	_ = s[0] // line 5: bounds check
	_ = s[1] // line 6: bounds check
	_ = s[2] // line 7: bounds check
}

func f2(s []int) {
	_ = s[2] // line 11: bounds check
	_ = s[1] // line 12: bounds check eliminated!
	_ = s[0] // line 13: bounds check eliminated!
}

func f3(s []int, index int) {
	_ = s[index] // line 17: bounds check
	_ = s[index] // line 18: bounds check eliminated!
}

func f4(a [5]int) {
	_ = a[4] // line 22: bounds check eliminated!
}

func main() {}
</code></pre>

<pre class="output"><code>$ go run -gcflags="-d=ssa/check_bce" example1.go
./example1.go:5: Found IsInBounds
./example1.go:6: Found IsInBounds
./example1.go:7: Found IsInBounds
./example1.go:11: Found IsInBounds
./example1.go:17: Found IsInBounds
</code></pre>

<p>
We can see that there are no needs to do bounds checks for line <i>12</i>
and line <i>13</i> in function <code>f2</code>,
for the bounds check at line <i>11</i> ensures that the indexes in
line <i>12</i> and line <i>13</i> will not be out of range.
</p>

<p>
But in function <code>f1</code>, bounds checks must be performed for all three lines.
The bounds check at line <i>5</i> can't ensure line <i>6</i>
and line <i>7</i> are safe,
and the bounds check at line <i>6</i> can't ensure line <i>7</i> is safe.
</p>

<p>
For function <code>f3</code>, the compiler knows the second
<code>s[index]</code> is absolutely safe if the first <code>s[index]</code>
is safe.
</p>

<p>
The compiler also correctly thinks the only line (line <i>22</i>)
in function <code>f4</code> is safe.
</p>

<p>
Please note that, up to now (Go Toolchain 1.25.n), the standard compiler
doesn't check BCE for an operation in a generic function if the operation
involves type parameters and the generic function is never instantiated.
</p>

A demo case:

<pre class="line-numbers must-line-numbers"><code class="language-go">// example1b.go
package main

func foo[E any](s []E) {
	_ = s[0] // line 5
	_ = s[1] // line 6
	_ = s[2] // line 7
}

// var _ = foo[bool]

func main() {
}
</code></pre>

When the variable declaration line is disabled, the compiler outputs nothing:

<pre class="output"><code>$ go run -gcflags="-d=ssa/check_bce" example1b.go
</code></pre>

<p>
</p>

When the variable declaration line is enabled, the compiler outputs:

<pre class="output"><code>./aaa.go:5:7: Found IsInBounds
./example1b.go:6:7: Found IsInBounds
./example1b.go:7:7: Found IsInBounds
./example1b.go:4:6: Found IsInBounds
</code></pre>

<p>
</p>

</div>

<h3>Example 2</h3>

<div>
<pre class="line-numbers must-line-numbers"><code class="language-go">// example2.go
package main

func f5(s []int) {
	for i := range s {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f6(s []int) {
	for i := 0; i < len(s); i++ {
		_ = s[i]
		_ = s[i:len(s)]
		_ = s[:i+1]
	}
}

func f7(s []int) {
	for i := len(s) - 1; i >= 0; i-- {
		_ = s[i]
		_ = s[i:len(s)]
	}
}

func f8(s []int, index int) {
	if index >= 0 && index < len(s) {
		_ = s[index]
		_ = s[index:len(s)]
	}
}

func f9(s []int) {
	if len(s) > 2 {
	    _, _, _ = s[0], s[1], s[2]
	}
}

func main() {}
</code></pre>

<pre class="output"><code>$ go run -gcflags="-d=ssa/check_bce" example2.go
</code></pre>

<p>
Cool! The standard compiler removes all bound checks in this program.
</p>

<p>
Note: before Go Toolchain version 1.11, the standard compiler is not smart enough to detect
line <i>22</i> is safe.
</p>

</div>

<h3>Example 3</h3>

<div>
<pre class="line-numbers must-line-numbers"><code class="language-go">// example3.go
package main

import "math/rand"

func fa() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	index := rand.Intn(7)
	_ = s[:index] // line 9: bounds check
	_ = s[index:] // line 10: bounds check eliminated!
}

func fb(s []int, i int) {
	_ = s[:i] // line 14: bounds check
	_ = s[i:] // line 15: bounds check, not smart enough?
}

func fc() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	i := rand.Intn(7)
	_ = s[:i] // line 22: bounds check
	_ = s[i:] // line 23: bounds check, not smart enough?
}

func main() {}
</code></pre>

<pre class="output"><code>$ go run -gcflags="-d=ssa/check_bce" example3.go
./example3.go:9: Found IsSliceInBounds
./example3.go:14: Found IsSliceInBounds
./example3.go:15: Found IsSliceInBounds
./example3.go:22: Found IsSliceInBounds
./example3.go:23: Found IsSliceInBounds
</code></pre>

<p>
Oh, so many places still need to do bounds check!
</p>

<p>
But wait, why does the standard Go compiler think line <i>10</i>
is safe but line <i>15</i> and line <i>23</i> are not?
Is the compiler still not smart enough?
</p>

<p>
In fact, the compiler is right here! Why?
The reason is the start index in a subslice expression may be larger than the length of the base slice.
Let's view a simple example:
</p>

<pre class="line-numbers must-line-numbers"><code class="language-go">package main

func main() {
	s0 := make([]int, 5, 10) // len(s0) == 5, cap(s0) == 10

	index := 8

	// In Go, for the subslice syntax s[a:b],
	// the relations 0 <= a <= b <= cap(s) must
	// be ensured to avoid panicking.

	_ = s0[:index]
	// The above line is safe can't ensure the
	// following line is also safe. In fact, the
	// following line will panic, for the starting
	// index is larger than the end index.
	_ = s0[index:] // panic
}
</code></pre>

<p>
So the conclusion that <b>if <code>s[:index]</code> is safe then <code>s[index:]</code>
is also safe</b> is only right when <code>len(s)</code> is equal to <code>cap(s)</code>.
This is why the code lines in function <code>fb</code> and <code>fc</code>
of example 3 still need to do bounds checks.
</p>

<p>
Standard Go compiler successfully detects <code>len(s)</code> is equal to
<code>cap(s)</code> in function <code>fa</code>.
Great work! Go team!
</p>

</div>

<h3>Example 4</h3>

<div>
<pre class="line-numbers must-line-numbers"><code class="language-go">// example4.go
package main

import "math/rand"

func fb2(s []int, index int) {
	_ = s[index:] // line 7: bounds check
	_ = s[:index] // line 8: bounds check eliminated!
}

func fc2() {
	s := []int{0, 1, 2, 3, 4, 5, 6}
	s = s[:4]
	index := rand.Intn(7)
	_ = s[index:] // line 15 bounds check
	_ = s[:index] // line 16: bounds check eliminated!
}

func main() {}
</code></pre>

<pre class="output"><code>$ go run -gcflags="-d=ssa/check_bce" example4.go
./example4.go:7:7: Found IsSliceInBounds
./example4.go:15:7: Found IsSliceInBounds
</code></pre>

In this example, The standard Go compiler successfully concludes
<ul>
<li>
	line <i>8</i> is also safe if line <i>7</i> is safe in function <code>fb2</code>.
</li>
<li>
	line <i>16</i> is also safe if line <i>15</i> is safe in function <code>fc2</code>.
</li>
</ul>

<p>
Note: the standard Go compiler in Go Toolchain earlier than version 1.9 fails to
detect line <i>8</i> doesn't need bounds check.
</p>

</div>

<h3>Example 5</h3>

<div>
The current version of the standard Go compiler is not smart
enough to eliminate all unnecessary bounds checks.
Sometimes, we can make some hints to help the compiler eliminate some unnecessary bounds checks.

<pre class="line-numbers must-line-numbers"><code class="language-go">// example5.go
package main

func fd(is []int, bs []byte) {
	if len(is) >= 256 {
		for _, n := range bs {
			_ = is[n] // line 7: bounds check
		}
	}
}

func fd2(is []int, bs []byte) {
	if len(is) >= 256 {
		is = is[:256] // line 14: a hint
		for _, n := range bs {
			_ = is[n] // line 16: BCEed!
		}
	}
}

func main() {}
</code></pre>

<!--
since Go Toolchain 1.11, the compiler becomes more smarter

func ff(s []int) []int {
	s2 := make([]int, len(s))
	for i := range s {
		s2[i] = -s[i] // line 41: bounds check, not smart enough
	}
	return s2
}

func ff2(s []int) []int {
	s2 := make([]int, len(s))
	s2 = s2[:len(s)] // line 48: to avoid bounds check at line 50
	for i := range s {
		s2[i] = -s[i] // line 50: bounds check eliminated!
	}
	return s2
}
-->

<pre class="output"><code>$ go run -gcflags="-d=ssa/check_bce" example5.go
./example5.go:7: Found IsInBounds
</code></pre>
</div>

<!--
<a class="anchor" id="slice-comparison"></a>
<h3>A Use Case of BCE: Efficient Slice Comparison</h3>

<p><b><i>
(Note: as Erik Dubbelboer pointed out, <a href="https://github.com/go101/go101/issues/64">the trick shown in this section
to optimize slice comparisons is not needed any more since Go Toolchain 1.11</a>.
The standard Go compiler 1.11+ becomes even smarter so that this trick is not needed ay more.
I will remove this section after some time.)
</i></b></p>

<div>

<p>
We all know that slice types don't support comparison in Go.
To compare two slices, we must write custom comparison code,
or use the <code>DeepEqual</code> function in the <code>reflect</code>
standard package. But the <code>reflect.DeepEqual</code> function is too slow.
</p>

The following is a custom slice comparison function.

<pre class="line-numbers"><code class="language-go">func CompareSlices_General(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}

	if (a == nil) != (b == nil) {
		return false
	}

	for i, v := range a {
		if v != b[i] { // here bounds check is needed for b[i]
			return false
		}
	}

	return true
}
</code></pre>

Bounds check is still needed for the <code>b[i]</code> in the
<code>for-range</code> loop block to avoid index <code>i</code> out of range.
We can modify the function a bit to remove the bounds check.

<pre class="line-numbers"><code class="language-go">func CompareSlices_BCE(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}

	if (a == nil) != (b == nil) {
		return false
	}

	b = b[:len(a)] // this line is the key.
	for i, v := range a {
		if v != b[i] { // no bounds check for b[i] now!
			return false
		}
	}

	return true
}
</code></pre>

Let's <a href="https://github.com/go101/go-benchmarks/blob/master/bce/bce_test.go">benchmark the two functions</a>.
The result (update: no differences for the standard compiler 1.11+):

<pre class="output"><code>Benchmark_SliceComparison/General-4         	 5000000	       287 ns/op
Benchmark_SliceComparison/BCE-4             	 5000000	       251 ns/op
</code></pre>

<p>
The BCE version is about 12.5% faster than the general version.
Really not bad.
</p>

</div>
-->

<h3>Summary</h3>

<p>
There are more BCE optimizations made by the standard Go compiler.
They might be not as obvious as the above listed ones,
So this article will not show them all.
</p>

<p>
Although the BCE feature in the standard Go compiler is still not perfect,
it really does well for many common cases.
It is no doubt that standard Go compiler will do better in later versions
so that it is possible the hints made in the above 5th example will become unnecessary.

Thank Go team for adding this wonderful feature!
</p>

<h3>References:</h3>
<div>
<ol>
<li><a href="https://docs.google.com/document/d/1vdAEAjYdzjnPA9WDOQ1e4e05cYVMpqSxJYZT33Cqw2g">Bounds Check Elimination</a></li>
<li>
	<a href="https://talks.godoc.org/github.com/klauspost/talks/2016/go17-compiler.slide">Utilizing the Go 1.7 SSA Compiler</a>
	(and <a href="https://talks.godoc.org/github.com/klauspost/talks/2016/go17-compiler-2.slide">the second part</a>)
</li>
</ol>
</div>

<!--
<p class="well well-sm">
[edit@2016/09/22] added example 5 and refs.
</p>
-->
</div>
